package org.mar.sort;

public class QuickSort implements Sort {

    public static void main(String[] args) {
        SortUtil.testSorted(new QuickSort());
    }

    @Override
    public void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        sort(array, 0, array.length);
    }

    private void sort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int p = array[start];
        int i = start, j = end;
        while (i < j) {
            while (j > i) {
                if (array[--j] < p) {
                    break;
                }
            }
            while (i < j) {
                if (array[++i] > p) {
                    break;
                }
            }
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
        int tmp = array[i];
        array[i] = p;
        array[start] = tmp;

        sort(array, start, i);
        sort(array, i + 1, end);
    }
}
